Problems tagged with topological sorting

Problems tagged with "topological sorting"

Problem #267

Consider the graph $G = (V, E)$ with $V = \{a, b, c\}$ and $E = \{(a, b)\}$.

How many valid topological sorts of this graph are there?

Solution

Problem #269

Let $G = (V,E)$ be the directed graph with $V = \{a, b, c, d, e\}$ and $E = \{(a, b), (a, c), (a, d), (b, e), (c, e), (d, e)\}$. How many valid topological sorts of $V$ are there?

Solution

Problem #270

Tags: topological sorting

Find a topological sort of the graph shown below:

Solution

d a b c e

Problem #297

Tags: topological sorting

Suppose $G$ is an acyclic directed graph. Let $a$ and $b$ be two nodes of $G$ such that $a$ appears before $b$ in every possible topological sort of $G$.

True or False: there must be a path from $a$ to $b$.

True False

Solution

True.

Suppose there were no path from $a$ to $b$. Then $a$ is not among the nodes that have a path to $b$. We could list $b$ and all the nodes with a path to $b$ first (in topological order), followed by the rest. This is a valid topological sort with $b$ before $a$.